public class Sort {

    /**
     * 堆排序
     * 时间复杂度：O(n*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        createHeap(array);
        int end = array.length - 1;
        while(end > 0) {
            swap(array,0,end);
            //调整的结束条件 变为 end，之后再 end--
            siftDown(array,0,end);
            end--;
        }
    }

    //创建一个大根堆
    public static void createHeap(int[] array){
        for (int i = (array.length-1-1)/2; i >= 0; i--) {
            siftDown(array,i,array.length);
        }
    }

    /**
     *
     * @param array
     * @param parent 每棵子树调整的根节点
     * @param length 每棵子树调整的结束节点
     */

    private static void siftDown(int[] array, int parent, int length) {
        int child = 2 * parent + 1;
        while(child < length) {
            if(child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,parent,child);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

}
